//
// Created by pangy on 2025/5/11.
//

#ifndef LINKLIST_H
#define LINKLIST_H

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "Status.h"

/**
 * 线性链表元素定义
 * 用于多项式
 * */
typedef struct {
    float coef;     // 系数
    int   expn;     // 指数
} ElemType;

/**
 * 线性链表结点结构
 * */
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *Link, *Position;

/**
 * 维护线性链表头尾指针及长度
 * */
typedef struct {
    Link head, tail;                // 头结点,尾结点
    int len;                        // 链表长度(线性链表中元素个数)
} LinkList;

/* 线性表基本操作 链表实现 */


/*--------------------------------内存操作-----------------------------------*/
/**
 * 分配结点空间,创建结点p, 值为e.
 * @param p 指向结点的指针
 * @param e 结点值
 * @return OK/ERROR
 */
Status MakeNode(Link* p, ElemType e);

/**
 * 释放结点空间
 * @param p 指向结点的指针
 */
void FreeNode(Link* p);


/*---------------------------------链表常规操作------------------------*/
/**
 * 构造一个空的链表 L
 * 成功返回OK,失败返回ERROR
*/
Status InitList(LinkList* L);

/**
 * 销毁线性表
 * 成功返回OK, 失败返回ERROR
 * */
Status DestroyList(LinkList* L);

/**
 * 清空线性表, 释放原链表的节点空间
 * 成功返回OK,失败返回ERROR
*/
Status ClearList(LinkList* L);

/**
 * 线性表长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(LinkList L);

/**
 * 首先查找与元素e满足Compare()==0的元素, 若找到,使用q存储其引用,并返回True,
 * 如果不存在上述引用,则查找首个满足Compare() > 0 的元素的前驱, 并返回False
 * 若链表中所有元素都大于e,则q存储头结点引用
 * 若链表中所有元素都小于e,则q存储尾结点引用
 * 其他情况,q置空
 */
Status LocateElem(LinkList L, ElemType e, Position* q, Status (Compare)(ElemType, ElemType));


/**
 * 将s结点插入到h节点后面
 */
Status InsertFirst(LinkList *L, Link h, Link s);

/**
 * 删除h结点后面第一个结点
 */
Status DeleteFirst(LinkList *L, Link h, Link* q);

/**
 * 将结点s追加到链表L末尾
 * @param L 链表
 * @param s 结点
 * @return ok/ERROR
 */
Status Append(LinkList* L, Link s);

/**
 * 更新结点数据域
 * @param p 结点
 * @param e 数据
 * @return OK/ERROR
 */
Status SetCurElem(Link p, ElemType e);

/**
 * 获取结点数据域
 * @param p
 * @param e
 * @return
 */
ElemType GetCurElem(Link p);

/**
 * 返回链表头结点
 * @param L
 * @return
 */
Position GetHead(LinkList L);

/**
 * 返回指定结点的后继, 不存在则返回NULL
 * @param L
 * @param p
 * @return
 */
Position NextPos(LinkList L, Link p);

#endif //LINKLIST_H
